{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Brace Expansion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #string #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #字符串 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: expand"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #花括号展开"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个表示单词列表的字符串&nbsp;<code>s</code>&nbsp;。单词中的每个字母都有一个或多个选项。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果有一个选项，则字母按原样表示。</li>\n",
    "\t<li>如果有多个选项，则用大括号分隔选项。例如,<meta charset=\"UTF-8\" />&nbsp;&nbsp;<code>\"{a,b,c}\"</code>&nbsp; 表示选项<meta charset=\"UTF-8\" />&nbsp;&nbsp;<code>[\"a\", \"b\", \"c\"]</code>&nbsp; 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>例如，如果<meta charset=\"UTF-8\" />&nbsp;&nbsp;<code>s = \"a{b,c}\"</code>&nbsp; ，第一个字符总是 <code>'a'</code> ，但第二个字符可以是 <code>'b'</code> 或 <code>'c'</code> 。原来的列表是<meta charset=\"UTF-8\" />&nbsp;<code>[\"ab\", \"ac\"]</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你 <strong>按字典顺序</strong> ，返回所有以这种方式形成的单词。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"{a,b}c{d,e}f\"\n",
    "<strong>输出：</strong>[\"acdf\",\"acef\",\"bcdf\",\"bcef\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcd\"\n",
    "<strong>输出：</strong>[\"abcd\"]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= S.length &lt;= 50</code></li>\n",
    "\t<li><meta charset=\"UTF-8\" /><code>s</code>&nbsp;由括号 <code>'{}'</code>&nbsp;, <code>','</code> 和小写英文字母组成。</li>\n",
    "\t<li><meta charset=\"UTF-8\" /><code>s</code>&nbsp;保证是一个有效的输入。</li>\n",
    "\t<li>没有嵌套的大括号。</li>\n",
    "\t<li>在一对连续的左括号和右括号内的所有字符都是不同的。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [brace-expansion](https://leetcode.cn/problems/brace-expansion/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [brace-expansion](https://leetcode.cn/problems/brace-expansion/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"{a,b}c{d,e}f\"', '\"abcd\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        ans=list() #the answer list, all possible path\n",
    "        stack=list()\n",
    "        tmp=list()\n",
    "        def dfs(x):\n",
    "            if x==len(graph)-1:\n",
    "                ans.append(stack[:]) #stack[:]和stack区别?\n",
    "                return \n",
    "\n",
    "            for y in graph[x]: #[1,2]\n",
    "                stack.append(y) #[0,1] 前进\n",
    "                dfs(y) #for 1, run dfs, expand the solution tree for y\n",
    "                stack.pop() #after dfs pop it.  回溯\n",
    "        \n",
    "        stack.append(0)\n",
    "        dfs(0) #start from root\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        pre = {\"\"}\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if s[i] == \"{\":\n",
    "                j = i\n",
    "                while s[i] != '}':\n",
    "                    i += 1\n",
    "                lst = s[j+1:i].split(\",\")\n",
    "                nex= set()\n",
    "                for p in pre:\n",
    "                    for x in lst:\n",
    "                        nex.add(p+x)\n",
    "                pre = nex\n",
    "                i += 1\n",
    "            else:\n",
    "                nex = set()\n",
    "                x = s[i]\n",
    "                for p in pre:\n",
    "                    nex.add(p + x)\n",
    "                pre = nex\n",
    "                i += 1\n",
    "        return sorted(pre)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        if '{' not in s:\n",
    "            return [s]\n",
    "\n",
    "        pre,rest = s.split('{',1)\n",
    "        options,rest = rest.split('}',1)\n",
    "        options = sorted(options.split(','))\n",
    "        result = []\n",
    "        for option in options:\n",
    "            for word in self.expand(rest):\n",
    "                result.append(pre + option + word)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        stack = []\n",
    "        candidates = []\n",
    "\n",
    "        in_bracket = False\n",
    "        for c in s:\n",
    "            if c == '{':\n",
    "                in_bracket = True\n",
    "            elif c == '}':\n",
    "                stack.append(sorted(candidates))\n",
    "                candidates = []\n",
    "                in_bracket = False\n",
    "            elif c == ',':\n",
    "                continue\n",
    "            else:\n",
    "                if in_bracket:\n",
    "                    candidates.append(c)\n",
    "                else:\n",
    "                    stack.append([c])\n",
    "\n",
    "        N = len(stack)\n",
    "        res = []\n",
    "        path = ''\n",
    "\n",
    "        print(stack)\n",
    "        res = self.travel(res, path, 0, N, stack)\n",
    "        return res\n",
    "\n",
    "\n",
    "        \n",
    "    def travel(self, res, path, i, N, candidates):\n",
    "        \"\"\"\n",
    "            i : search in candidates[i]\n",
    "            j : start idx of candidates[i]\n",
    "        \"\"\"\n",
    "        if i == N:\n",
    "            res.append(path)\n",
    "            return res\n",
    "        \n",
    "        for idx in range(len(candidates[i])):\n",
    "            self.travel(res, path + candidates[i][idx], i+1, N, candidates)\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        par_data=[]\n",
    "        cur=[]\n",
    "        flag=0\n",
    "        for x in s:\n",
    "            if x==\"{\":\n",
    "                flag=1#启动括号模式\n",
    "                cur=[]\n",
    "            elif x==\"}\":\n",
    "                par_data.append(cur)\n",
    "                cur=[]\n",
    "                flag=0\n",
    "            elif x!=\"{\" and x!=\",\" and flag==0 :\n",
    "                cur.append(x)\n",
    "                par_data.append(cur)\n",
    "                cur=[]\n",
    "            elif x!=\"{\" and x!=\",\" and flag==1:\n",
    "                cur.append(x)\n",
    "            else:\n",
    "                continue\n",
    "        # print(par_data)\n",
    "        def track(cur_result,finall_result,n,start_index,data):\n",
    "            if len(cur_result)==n:\n",
    "                print(cur_result)\n",
    "                finall_result.append(cur_result)\n",
    "                return finall_result\n",
    "            if start_index>=n:\n",
    "                return finall_result\n",
    "            for i in range(len(data[start_index])):\n",
    "                finall_result=track(cur_result+data[start_index][i],finall_result,n,start_index+1,data)\n",
    "            return finall_result\n",
    "        finall_result=[]\n",
    "        track(\"\",finall_result,len(par_data),0,par_data)\n",
    "        finall_result.sort()\n",
    "        return finall_result\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result = []\n",
    "        self.arr = []\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            if s[i] == '{':\n",
    "                for j in range(i+1, len(s)):\n",
    "                    if s[j] == '}':\n",
    "                        break\n",
    "                self.arr.append(sorted(s[i+1:j].split(',')))\n",
    "                i = j+1\n",
    "            else:\n",
    "                self.arr.append([s[i]])\n",
    "                i += 1\n",
    "        self.dfs(0, '')\n",
    "        return self.result\n",
    "\n",
    "    def dfs(self, idx, s):\n",
    "        if idx == len(self.arr):\n",
    "            self.result.append(s[:])\n",
    "            return\n",
    "        for each in self.arr[idx]:\n",
    "            self.dfs(idx + 1, s + each)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        idxs = []\n",
    "\n",
    "        for i, w in enumerate(s):\n",
    "            if w in ('{', '}'):\n",
    "                idxs.append(i)\n",
    "        \n",
    "        if len(idxs) == 0:\n",
    "            return [s]\n",
    "        else:\n",
    "            first_pair = idxs[:2]\n",
    "            fst, sed = first_pair\n",
    "            ret = []\n",
    "\n",
    "            for r in self.expand(s[sed+1:]):\n",
    "                for w in s[fst+1: sed].split(','):\n",
    "                    ret.append(\n",
    "                        s[:fst] + w + r\n",
    "                    )\n",
    "            return sorted(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        if '{' not in s:\n",
    "            return [s]\n",
    "        pre,rest = s.split('{',1)\n",
    "        options,rest = rest.split('}',1)\n",
    "        options = sorted(options.split(','))\n",
    "        res = []\n",
    "        for option in options:\n",
    "            for word in self.expand(rest):\n",
    "                res.append(pre + option + word)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        \n",
    "        def dfs(s):\n",
    "            if len(s)==0:\n",
    "                return []\n",
    "            i = 0\n",
    "            mutate = []\n",
    "            path = \"\"\n",
    "            while(i<len(s) and s[i]!='{'):\n",
    "                path+=s[i]\n",
    "                i+=1\n",
    "            j = i\n",
    "            while(j<len(s) and s[j]!= '}'):\n",
    "                if s[j]!='{' and s[j]!=',':\n",
    "                    mutate.append(s[j])\n",
    "                j+=1\n",
    "            res = []\n",
    "            mutate.sort()\n",
    "            for string in mutate:\n",
    "                if j+1<len(s):\n",
    "                    for result in dfs(s[j+1:]):\n",
    "                        res.append(path+string+result)\n",
    "                else:\n",
    "                    res.append(path+string)\n",
    "            if not mutate:\n",
    "                res.append(path)\n",
    "            return res\n",
    "        \n",
    "        return dfs(s)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        def dfs(s):\n",
    "            if len(s) == 0:\n",
    "                return []\n",
    "            i = 0\n",
    "            candidate = []\n",
    "            path = \"\"\n",
    "            while i < len(s) and s[i] != \"{\": # 不需要变的\n",
    "                path += s[i]\n",
    "                i += 1\n",
    "            j = i\n",
    "            while j < len(s) and s[j] != \"}\": #{}里的，需要变\n",
    "                if s[j].isalpha(): #s[j] != \"{\" and s[j] != \",\":\n",
    "                    candidate.append(s[j])\n",
    "                j += 1\n",
    "            \n",
    "            anw = []\n",
    "            candidate.sort()\n",
    "            for st in candidate:\n",
    "                if j + 1 < len(s):\n",
    "                    for res in dfs(s[j+1:]):\n",
    "                        anw.append(path + st + res)\n",
    "                else:\n",
    "                    anw.append(path + st)\n",
    "            \n",
    "            if not candidate:\n",
    "                anw.append(path)\n",
    "            \n",
    "            return anw\n",
    "        \n",
    "        return dfs(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        def dfs(s):\n",
    "            if len(s) == 0:\n",
    "                return []\n",
    "            \n",
    "            mutate = []\n",
    "            path = \"\"\n",
    "\n",
    "            i = 0\n",
    "            while i < len(s) and s[i] != '{':\n",
    "                path += s[i]\n",
    "                i += 1\n",
    "            j = i\n",
    "            while j < len(s) and s[j] != '}':\n",
    "                if s[j] != '{' and s[j] != ',':\n",
    "                    mutate.append(s[j])\n",
    "                j += 1\n",
    "            \n",
    "            ans = []\n",
    "            mutate.sort()\n",
    "            for string in mutate:\n",
    "                if j + 1 < len(s):\n",
    "                    for result in dfs(s[j + 1:]):\n",
    "                        ans.append(path + string + result)\n",
    "                else:\n",
    "                    ans.append(path + string)\n",
    "            if not mutate:\n",
    "                ans.append(path)\n",
    "            return ans\n",
    "        \n",
    "        return dfs(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        start = s.find('{')\n",
    "        if start == -1:\n",
    "            return [s]\n",
    "        end = s.find('}')\n",
    "        prelist = self.expand(s[end+1:])\n",
    "        ans = []\n",
    "        split = s[start+1:end].split(',')\n",
    "        split.sort()\n",
    "        for i in split:\n",
    "            for j in prelist:\n",
    "                ans.append(s[:start]+i+j)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        # 将包含括号的字符串转换为嵌套的多维数组，以便后续处理 O(n^2)\n",
    "        def Brackets2NestedArray(s: str, left_mark='(', right_mark=')')->list[str]:\n",
    "            if not s: return []\n",
    "            def f(s):\n",
    "                if left_mark not in s: return [s]\n",
    "                rnt, cnt, t = [], 0, \"\"\n",
    "                for c in s:\n",
    "                    if c == left_mark:\n",
    "                        if cnt == 0 and t: rnt.append(t)\n",
    "                        cnt += 1\n",
    "                        t = \"\"\n",
    "                    elif c == right_mark:\n",
    "                        cnt -= 1\n",
    "                        if cnt == 0 and t: rnt.append(f(t))\n",
    "                        t = \"\"\n",
    "                    else: t += c\n",
    "                if t: rnt.append(t)\n",
    "                return rnt\n",
    "            return f(s)\n",
    "        nested_arr = Brackets2NestedArray(s, \"{\", \"}\") # s = \"(a,b)c(d,e)f\" -> [['a,b'], 'c', ['d,e'], 'f']\n",
    "        arr = []\n",
    "        for x in nested_arr:\n",
    "            if type(x) == type(\"\"): arr.append([x])\n",
    "            else: arr.append(list(x[0].split(\",\")))\n",
    "        return sorted([\"\".join(x) for x in product(*arr)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        def dfs(s):\n",
    "            if len(s) == 0:\n",
    "                return []\n",
    "            \n",
    "            mutate = []\n",
    "            path = \"\"\n",
    "\n",
    "            i = 0\n",
    "            while i < len(s) and s[i] != '{':\n",
    "                path += s[i]\n",
    "                i += 1\n",
    "            j = i\n",
    "            while j < len(s) and s[j] != '}':\n",
    "                if s[j] != '{' and s[j] != ',':\n",
    "                    mutate.append(s[j])\n",
    "                j += 1\n",
    "            \n",
    "            ans = []\n",
    "            mutate.sort()\n",
    "            for char in mutate:\n",
    "                if j + 1 < len(s):\n",
    "                    for result in dfs(s[j + 1:]):\n",
    "                        ans.append(path + char + result)\n",
    "                else:\n",
    "                    ans.append(path + char)\n",
    "            \n",
    "            if not mutate:\n",
    "                ans.append(path)\n",
    "            return ans\n",
    "        \n",
    "        return dfs(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        if s[0] == \"{\":\n",
    "            ss = []\n",
    "        else:\n",
    "            ss = [\"\"]\n",
    "        q = []\n",
    "        f = -1\n",
    "        for i in s:\n",
    "            if i == '{':\n",
    "                f = 0\n",
    "            elif i == '}':\n",
    "                q.sort()\n",
    "                ss.append(q[:])\n",
    "                q.clear()\n",
    "                f = -1\n",
    "                ss.append(\"\")\n",
    "            elif i!=',':\n",
    "                if f==0:\n",
    "                    q.append(i)\n",
    "                else:\n",
    "                    ss[-1]+=i\n",
    "        ans = []\n",
    "        n = len(ss)\n",
    "        def dfs(cur, start):\n",
    "            if start == n:\n",
    "                ans.append(cur)\n",
    "                return\n",
    "\n",
    "            if type(ss[start]) == str:\n",
    "                dfs(cur+ss[start], start+1)\n",
    "            else:\n",
    "                for ii in ss[start]:\n",
    "                    dfs(cur+ii, start+1)\n",
    "                \n",
    "        dfs(\"\", 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        par_data=[]\n",
    "        cur=[]\n",
    "        flag=0\n",
    "        for x in s:\n",
    "            if x==\"{\":\n",
    "                flag=1#启动括号模式\n",
    "                # if len(par_data)!=0:\n",
    "                #     par_data.append(cur)\n",
    "                cur=[]\n",
    "            elif x==\"}\":\n",
    "                par_data.append(cur)\n",
    "                cur=[]\n",
    "                flag=0\n",
    "            elif x!=\"{\" and x!=\",\" and flag==0 :\n",
    "                cur.append(x)\n",
    "                par_data.append(cur)\n",
    "                cur=[]\n",
    "            elif x!=\"{\" and x!=\",\" and flag==1:\n",
    "                cur.append(x)\n",
    "            else:\n",
    "                continue\n",
    "        # print(par_data)\n",
    "        def track(cur_result,finall_result,n,start_index,data):\n",
    "            if len(cur_result)==n:\n",
    "                print(cur_result)\n",
    "                finall_result.append(cur_result)\n",
    "                return finall_result\n",
    "            if start_index>=n:\n",
    "                return finall_result\n",
    "            for i in range(len(data[start_index])):\n",
    "                finall_result=track(cur_result+data[start_index][i],finall_result,n,start_index+1,data)\n",
    "            return finall_result\n",
    "        finall_result=[]\n",
    "        track(\"\",finall_result,len(par_data),0,par_data)\n",
    "        finall_result.sort()\n",
    "        return finall_result\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        q=[]\n",
    "        rem=[]\n",
    "        ls=[]\n",
    "        mark=False\n",
    "        for ch in s:\n",
    "            if ch==\"{\":\n",
    "                mark=True\n",
    "            elif ch==\"}\":\n",
    "                mark=False\n",
    "                rem.append(copy.deepcopy(ls))\n",
    "                ls=[]\n",
    "            else:\n",
    "                if ch==\",\":\n",
    "                    continue\n",
    "                if mark:\n",
    "                    ls.append(ch)\n",
    "                else:\n",
    "                    rem.append([ch])\n",
    "        n=len(rem)\n",
    "        ans=[]\n",
    "        def find(x,now):\n",
    "            if x==n:\n",
    "                ans.append(\"\".join(now))\n",
    "                return \n",
    "            for ch in rem[x]:\n",
    "                now.append(ch)\n",
    "                find(x+1,now)\n",
    "                now.pop()\n",
    "        find(0,[])\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        start = s.find('{')\n",
    "        if start == -1:\n",
    "            return [s]\n",
    "        end = s.find('}')\n",
    "        prelist = self.expand(s[end+1:])\n",
    "        ans = []\n",
    "        split = s[start+1:end].split(',')\n",
    "        split.sort()\n",
    "        for i in split:\n",
    "            for j in prelist:\n",
    "                ans.append(s[:start]+i+j)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        stack=[]\n",
    "        arr=[]\n",
    "        f=0\n",
    "        for i,v in enumerate(s):\n",
    "            if v==\"{\":\n",
    "                f=1\n",
    "            elif v.isalpha():\n",
    "                if f==1:\n",
    "                    stack.append(v)\n",
    "                else:\n",
    "                    arr.append(v)\n",
    "            elif v==\"}\":\n",
    "                arr.append(stack)\n",
    "                stack=[]\n",
    "                f=0\n",
    "        ans=[]\n",
    "        n=len(arr)\n",
    "        def dfs(i,t):\n",
    "            if i==n:\n",
    "                ans.append(t)\n",
    "                return \n",
    "            \n",
    "            for nex in arr[i]:\n",
    "                dfs(i+1,t+nex)\n",
    "            #else 1:\n",
    "              #  dfs(i+1,t+arr[i])\n",
    "        dfs(0,\"\")\n",
    "        return sorted(ans )\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        if True:\n",
    "            s_list, word = [], \"\"\n",
    "            for c in s:\n",
    "                if c in \"{}\": \n",
    "                    s_list.append(word)\n",
    "                    word = \"\"\n",
    "                else:\n",
    "                    word+=c\n",
    "            if word: s_list.append(word)\n",
    "            s_list = [i.split(\",\") for i in s_list]\n",
    "            print(s_list)\n",
    "\n",
    "            results = []\n",
    "            def dfs(paths, index):\n",
    "                if len(paths) == len(s_list):\n",
    "                    results.append(\"\".join(paths))\n",
    "                    return\n",
    "                for i in range(len(s_list[index])):\n",
    "                    dfs(paths + [s_list[index][i]], index+1)\n",
    "            dfs([], 0)\n",
    "            return sorted(results)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        else:\n",
    "            import re\n",
    "            words = [i.split(\",\") for i in re.split(r\"{|}\", s) if i]\n",
    "            \n",
    "            results = []\n",
    "\n",
    "            def dfs(paths, index):\n",
    "                if len(paths) == len(words):\n",
    "                    results.append(paths)\n",
    "                    return\n",
    "\n",
    "                for i, c in enumerate(words[index]):\n",
    "                    dfs(paths + [c], index+1)\n",
    "            dfs([], 0)\n",
    "            results = [\"\".join(i) for i in results]\n",
    "            print(results)\n",
    "            return sorted(results)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "{a,b}c{d,e}f\n",
    "[[a, b], [c], [d, e]]\n",
    "同意list中的格式\n",
    "\n",
    "因为\n",
    "\n",
    "a -> c -> d\n",
    "\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        tokens = []\n",
    "        i = 0\n",
    "\n",
    "        while i < len(s):\n",
    "            if s[i] == '{':\n",
    "                j = i + 1\n",
    "                while s[j] != '}':\n",
    "                    j += 1\n",
    "                \n",
    "                tokens.append(sorted(s[i+1:j].split(',')))\n",
    "                i = j + 1\n",
    "            else:\n",
    "                tokens.append([s[i]])\n",
    "                i += 1\n",
    "        \n",
    "        res = []\n",
    "\n",
    "        def dfs(start, cur):\n",
    "            if start == len(tokens):\n",
    "                res.append(''.join(cur))\n",
    "                return\n",
    "            \n",
    "            for token in tokens[start]:\n",
    "                dfs(start + 1, cur + [token])\n",
    "\n",
    "        dfs(0, [])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "\n",
    "\n",
    "        s=list(s.replace(\",\",\"\"))\n",
    "        res=[]\n",
    "        def backtrack(p,l):\n",
    "            if not l:\n",
    "                res.append(p)\n",
    "                return\n",
    "\n",
    "            if l[0]!='{':\n",
    "                backtrack(p+l[0],l[1:])\n",
    "            else:\n",
    "                j=0\n",
    "                while l[j]!='}':\n",
    "                    j+=1\n",
    "                for i in range(1,j):\n",
    "                    if i!=',':\n",
    "                        backtrack(p+l[i],l[j+1:])\n",
    "        backtrack('',s)\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        results = []\n",
    "        word = []  \n",
    "        self.dfsHelper(s,0,word,results)\n",
    "        return [''.join(word) for word in results]\n",
    "\n",
    "    def dfsHelper(self,s,start,word,results):\n",
    "        if start == len(s):\n",
    "            results.append(word.copy())\n",
    "            return \n",
    "        if s[start] != '{':\n",
    "            word.append(s[start])\n",
    "            self.dfsHelper(s,start+1,word,results)\n",
    "            word.pop()\n",
    "        else:\n",
    "            temp = []\n",
    "            start = start + 1 \n",
    "            end = start +1\n",
    "            temp.append(s[start])\n",
    "            while s[end] != '}':\n",
    "                if s[end] != ',':\n",
    "                    temp.append(s[end])\n",
    "                end += 1\n",
    "            temp.sort()\n",
    "            for char in temp:\n",
    "                word.append(char)\n",
    "                self.dfsHelper(s,end + 1,word,results)\n",
    "                word.pop()\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        t0=[]\n",
    "        t0=s.split('}')\n",
    "        t1=[]\n",
    "        for i in t0:\n",
    "            t1=t1+ i.split('{')\n",
    "        t2=[]\n",
    "        for i in t1:\n",
    "            if i!='':\n",
    "                t2.append(i)\n",
    "        print(t2)\n",
    "        t=[[] for i in range(len(t2))]\n",
    "        for i in range(len(t2)):\n",
    "            t[i]=t2[i].split(',')\n",
    "        print(t)\n",
    "        ans=[]\n",
    "        def f(i,tmp):\n",
    "            if i==len(t):\n",
    "                nonlocal ans\n",
    "                ans.append(tmp)\n",
    "                return\n",
    "            now=t[i]\n",
    "            for st in now:\n",
    "                f(i+1,tmp+st)\n",
    "        f(0,'')\n",
    "        ans.sort()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        res = []\n",
    "        flag = False\n",
    "        st = []\n",
    "        while i < n:\n",
    "            if s[i] == '{':\n",
    "                flag = True\n",
    "            elif s[i] == '}':\n",
    "                ans = []\n",
    "                while st:\n",
    "                    cur = st.pop()\n",
    "                    if cur != ',':\n",
    "                        ans.append(cur)\n",
    "                ans.sort()\n",
    "                st = []\n",
    "                res.append(ans)\n",
    "                flag = False\n",
    "            else:\n",
    "                if flag == True:\n",
    "                    st.append(s[i])\n",
    "                else:\n",
    "                    res.append([s[i]])\n",
    "            i += 1\n",
    "        ans = []\n",
    "        n = len(res)\n",
    "        def dfs(i, path):\n",
    "            if i == n:\n",
    "                ans.append(path)\n",
    "                return ans\n",
    "            for j in res[i]:\n",
    "                dfs(i + 1, path + j)\n",
    "            return ans\n",
    "        dfs(0, '')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "        storage = []\n",
    "        flag = False\n",
    "        for ch in s:\n",
    "            if ch == ',':\n",
    "                pass\n",
    "            elif ch == '{':\n",
    "                storage.append([])\n",
    "                flag = True\n",
    "            elif ch == '}':\n",
    "                flag = False\n",
    "            else:\n",
    "                if flag:\n",
    "                    storage[-1].append(ch)\n",
    "                else:\n",
    "                    storage.append([ch])\n",
    "        print(storage)\n",
    "        n = len(storage)\n",
    "        def findans(pre, k):\n",
    "            if k == n:\n",
    "                ans.append(pre)\n",
    "            else:\n",
    "                items = storage[k]\n",
    "                for ch in items:\n",
    "                    pre = pre + ch\n",
    "                    findans(pre, k+1)\n",
    "                    pre = pre[:-1]\n",
    "        findans('', 0)\n",
    "        ans.sort()\n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        if not s: return []\n",
    "\n",
    "        i = 0\n",
    "        tokens = []\n",
    "\n",
    "        while i < len(s):\n",
    "            if s[i] == '{':\n",
    "                j = i + 1\n",
    "                while s[j] != '}':\n",
    "                    j += 1\n",
    "                tokens.append(sorted(s[i+1:j].split(',')))\n",
    "                i = j + 1\n",
    "            else:\n",
    "                tokens.append([s[i]])\n",
    "                i += 1\n",
    "        \n",
    "        res = []\n",
    "\n",
    "        def dfs(index, cur):\n",
    "            if index == len(tokens):\n",
    "                res.append(''.join(cur))\n",
    "                return\n",
    "            \n",
    "            for token in tokens[index]:\n",
    "                dfs(index + 1, cur + [token])\n",
    "\n",
    "        dfs(0, [])\n",
    "        return res\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        tokens = []\n",
    "        tmp = \"\"\n",
    "        for c in s:\n",
    "            if c == '}':\n",
    "                tokens.append(sorted(tmp[1:].split(',')))\n",
    "                tmp = \"\"\n",
    "            elif c == '{' or tmp:\n",
    "                tmp += c\n",
    "            else:\n",
    "                tokens.append(c)\n",
    "\n",
    "        ret = []\n",
    "        def dfs(i, prefix):\n",
    "            if i == len(tokens):\n",
    "                ret.append(\"\".join(prefix))\n",
    "                return\n",
    "\n",
    "            for c in tokens[i]:\n",
    "                prefix.append(c)\n",
    "                dfs(i + 1, prefix)\n",
    "                prefix.pop()\n",
    "        dfs(0, [])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        n, ans = len(s), []\n",
    "        def backtrack(i, hold):\n",
    "            if i == n:\n",
    "                ans.append(''.join(hold))\n",
    "                return\n",
    "            if s[i] == '{':\n",
    "                pre = i\n",
    "                while s[i] != '}':\n",
    "                    i += 1\n",
    "                sub = s[pre+1:i].split(',')\n",
    "                for c in sub:\n",
    "                    hold.append(c)\n",
    "                    backtrack(i+1, hold)\n",
    "                    hold.pop()\n",
    "            else:\n",
    "                hold.append(s[i])\n",
    "                backtrack(i+1, hold)\n",
    "                hold.pop()\n",
    "        backtrack(0, [])\n",
    "        return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        tokens = []\n",
    "        tmp = \"\"\n",
    "        for c in s:\n",
    "            if c == '}':\n",
    "                tokens.append(sorted(tmp[1:].split(',')))\n",
    "                tmp = \"\"\n",
    "            elif c == '{' or tmp:\n",
    "                tmp += c\n",
    "            else:\n",
    "                tokens.append(c)\n",
    "\n",
    "        ret = []\n",
    "        def work(i, prefix):\n",
    "            if i == len(tokens):\n",
    "                ret.append(\"\".join(prefix))\n",
    "                return\n",
    "\n",
    "            for c in tokens[i]:\n",
    "                prefix.append(c)\n",
    "                work(i + 1, prefix)\n",
    "                prefix.pop()\n",
    "        work(0, [])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        if True:\n",
    "            import re\n",
    "            s_list =[i.split(\",\") for i in re.split(r\"{|}\", s)]\n",
    "            \"\"\"\n",
    "            s_list, word = [], \"\"\n",
    "            for c in s:\n",
    "                if c in \"{}\": \n",
    "                    s_list.append(word)\n",
    "                    word = \"\"\n",
    "                else:\n",
    "                    word+=c\n",
    "            if word: s_list.append(word)\n",
    "            s_list = [i.split(\",\") for i in s_list]\n",
    "            \"\"\"\n",
    "            print(s_list)\n",
    "\n",
    "            results = []\n",
    "            def dfs(paths, index):\n",
    "                if len(paths) == len(s_list):\n",
    "                    results.append(\"\".join(paths))\n",
    "                    return\n",
    "                for i in range(len(s_list[index])):\n",
    "                    dfs(paths + [s_list[index][i]], index+1)\n",
    "            dfs([], 0)\n",
    "            results.sort()\n",
    "            return results\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        else:\n",
    "            import re\n",
    "            words = [i.split(\",\") for i in re.split(r\"{|}\", s) if i]\n",
    "            \n",
    "            results = []\n",
    "\n",
    "            def dfs(paths, index):\n",
    "                if len(paths) == len(words):\n",
    "                    results.append(paths)\n",
    "                    return\n",
    "\n",
    "                for i, c in enumerate(words[index]):\n",
    "                    dfs(paths + [c], index+1)\n",
    "            dfs([], 0)\n",
    "            results = [\"\".join(i) for i in results]\n",
    "            print(results)\n",
    "            return sorted(results)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        if True:\n",
    "            import re\n",
    "            s_list =[i.split(\",\") for i in re.split(r\"{|}\", s)]\n",
    "            \"\"\"\n",
    "            s_list, word = [], \"\"\n",
    "            for c in s:\n",
    "                if c in \"{}\": \n",
    "                    s_list.append(word)\n",
    "                    word = \"\"\n",
    "                else:\n",
    "                    word+=c\n",
    "            if word: s_list.append(word)\n",
    "            s_list = [i.split(\",\") for i in s_list]\n",
    "            \"\"\"\n",
    "            print(s_list)\n",
    "\n",
    "            results = []\n",
    "            def dfs(paths, index):\n",
    "                if len(paths) == len(s_list):\n",
    "                    results.append(\"\".join(paths))\n",
    "                    return\n",
    "                for i in range(len(s_list[index])):\n",
    "                    dfs(paths + [s_list[index][i]], index+1)\n",
    "            dfs([], 0)\n",
    "            return sorted(results)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        else:\n",
    "            import re\n",
    "            words = [i.split(\",\") for i in re.split(r\"{|}\", s) if i]\n",
    "            \n",
    "            results = []\n",
    "\n",
    "            def dfs(paths, index):\n",
    "                if len(paths) == len(words):\n",
    "                    results.append(paths)\n",
    "                    return\n",
    "\n",
    "                for i, c in enumerate(words[index]):\n",
    "                    dfs(paths + [c], index+1)\n",
    "            dfs([], 0)\n",
    "            results = [\"\".join(i) for i in results]\n",
    "            print(results)\n",
    "            return sorted(results)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        n, ans = len(s), []\n",
    "        def backtrack(i, hold):\n",
    "            if i == n:\n",
    "                ans.append(''.join(hold))\n",
    "                return\n",
    "            if s[i] == '{':\n",
    "                pre = i\n",
    "                while s[i] != '}':\n",
    "                    i += 1\n",
    "                sub = s[pre+1:i].split(',')\n",
    "                for c in sub:\n",
    "                    hold.append(c)\n",
    "                    backtrack(i+1, hold)\n",
    "                    hold.pop()\n",
    "            else:\n",
    "                hold.append(s[i])\n",
    "                backtrack(i+1, hold)\n",
    "                hold.pop()\n",
    "        backtrack(0, [])\n",
    "        return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        length, result = len(s), []\n",
    "\n",
    "        def _backtrack(index, hold):\n",
    "            if index == length:\n",
    "                result.append(\"\".join(hold))\n",
    "                return\n",
    "            \n",
    "            if s[index] == \"{\":\n",
    "                \n",
    "                pre = index\n",
    "\n",
    "                while s[index] != \"}\":\n",
    "                    index += 1\n",
    "                \n",
    "                sub = s[pre+1 : index].split(\",\")\n",
    "\n",
    "                for c in sub:\n",
    "                    hold.append(c)\n",
    "                    _backtrack(index+1, hold)\n",
    "                    hold.pop()\n",
    "\n",
    "\n",
    "            else:\n",
    "                hold.append(s[index])\n",
    "                _backtrack(index+1, hold)\n",
    "                hold.pop()\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        _backtrack(0, [])\n",
    "        return sorted(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        result = []\n",
    "        solution = []\n",
    "        def traverse(start: int):\n",
    "            if not start < len(s):\n",
    "                result.append(\"\".join(solution))\n",
    "                return\n",
    "            # 解析本层可能的选择 得到 items\n",
    "            items = [s[start]]\n",
    "            nxt = start + 1\n",
    "            if s[start] == \"{\":\n",
    "                while s[nxt] != \"}\":\n",
    "                    nxt += 1\n",
    "                items = s[start+1:nxt].split(\",\")\n",
    "                items.sort()\n",
    "                nxt += 1\n",
    "            # 更新下一层起始的位置\n",
    "            for item in items:\n",
    "                solution.append(item)\n",
    "                traverse(nxt)\n",
    "                solution.pop()\n",
    "        traverse(0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        import re\n",
    "        s_words = [i.split(\",\") for i in re.split(r\"{|}\", s) if i]\n",
    "        \n",
    "        res = []\n",
    "        def backtrace(paths, index):\n",
    "            if len(paths) == len(s_words):\n",
    "                res.append(\"\".join(paths))\n",
    "                return\n",
    "            for i in range(len(s_words[index])):\n",
    "                backtrace(paths + [s_words[index][i]], index+1)\n",
    "        backtrace([], 0)\n",
    "        return sorted(res)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        s = s.replace(\",\",\"\")\n",
    "        stack = []\n",
    "        for w in s:\n",
    "            if w==\"}\":\n",
    "                cur = []\n",
    "                while stack and stack[-1] != \"{\":\n",
    "                    cur.append(stack.pop())\n",
    "                stack.pop()\n",
    "                stack.append(\"\".join(sorted(cur)))\n",
    "            else:\n",
    "                stack.append(w)\n",
    "        def dfs(pre,i):\n",
    "            if i==n:\n",
    "                ans.append(pre)\n",
    "                return \n",
    "            for w in stack[i]:\n",
    "                dfs(pre+w,i+1)\n",
    "            return \n",
    "        \n",
    "        n = len(stack)\n",
    "        ans =[]\n",
    "        dfs(\"\",0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        s = s.replace(',', '')\n",
    "        stack = []\n",
    "        for w in s:\n",
    "            if w == '}':\n",
    "                cur = []\n",
    "                while stack and stack[-1] != '{':\n",
    "                    cur.append(stack.pop())\n",
    "                stack.pop()\n",
    "                stack.append(''.join(sorted(cur)))\n",
    "            else:\n",
    "                stack.append(w)\n",
    "        def dfs(path, index):\n",
    "            if index == n:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            for w in stack[index]:\n",
    "                dfs(path+w, index + 1)\n",
    "        res = []\n",
    "        n = len(stack)\n",
    "        dfs('', 0)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        def dfs(index, cur):\n",
    "            # print(cur)\n",
    "            if index == len(s):\n",
    "                nonlocal res\n",
    "                res = cur[::-1]\n",
    "                return\n",
    "            if s[index].isalpha():\n",
    "                temp = []\n",
    "                for c in cur:\n",
    "                    temp.append(c + s[index])\n",
    "                dfs(index+1, temp)\n",
    "            elif s[index] == '{':\n",
    "                start = index+1\n",
    "                while s[index] != '}':\n",
    "                    index += 1\n",
    "                queue = s[start:index].split(',')\n",
    "                temp = []\n",
    "                for c1 in queue:\n",
    "                    for c2 in cur:\n",
    "                        temp.append(c2+c1)\n",
    "                dfs(index+1, temp)\n",
    "        res = []\n",
    "        dfs(0, [''])\n",
    "        res.sort()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        n, ans = len(s), []\n",
    "\n",
    "        def dfs(i, path):\n",
    "            if i == n:\n",
    "                ans.append(''.join(path))\n",
    "                return \n",
    "            if s[i] == '{':\n",
    "                pre = i\n",
    "                while s[i] != '}':\n",
    "                    i += 1\n",
    "                sub = s[pre+1:i].split(',')\n",
    "                for c in sub:\n",
    "                    path.append(c)\n",
    "                    dfs(i+1, path)\n",
    "                    path.pop()\n",
    "            else:\n",
    "                path.append(s[i])\n",
    "                dfs(i+1, path)\n",
    "                path.pop()\n",
    "\n",
    "        dfs(0, [])\n",
    "        return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        def dfs(prefix: str, s: str) -> None:\n",
    "            #---- 剪枝\n",
    "            if not s:\n",
    "                self.res.append(prefix)\n",
    "                return\n",
    "            #---------- 第一个是‘{’ \n",
    "            if s[0].isalpha() == 0:\n",
    "                tmp = \"\"\n",
    "                i = 0\n",
    "                while i < len(s):\n",
    "                    if s[i] == '}':\n",
    "                        tmp = s[1:i]\n",
    "                        break\n",
    "                    i += 1\n",
    "                tmp = tmp.split(',')\n",
    "                tmp.sort()\n",
    "                for c in tmp:\n",
    "                    dfs(prefix + c, s[i+1 : ])\n",
    "            #---------- 第一个是子母\n",
    "            else:\n",
    "                i = 0\n",
    "                while i < len(s):\n",
    "                    if s[i] == '{':\n",
    "                        break\n",
    "                    i += 1\n",
    "                dfs(prefix + s[ :i], s[i: ])\n",
    "\n",
    "        self.res = []\n",
    "        dfs(\"\", s)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        import re\n",
    "        words = [i.split(\",\") for i in re.split(r\"{|}\", s) if i]\n",
    "        \n",
    "        results = []\n",
    "\n",
    "        def dfs(paths, index):\n",
    "            if len(paths) == len(words):\n",
    "                results.append(paths)\n",
    "                return\n",
    "\n",
    "            for i, c in enumerate(words[index]):\n",
    "                dfs(paths + [c], index+1)\n",
    "        dfs([], 0)\n",
    "        results = [\"\".join(i) for i in results]\n",
    "        print(results)\n",
    "        return sorted(results)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        ans, ele = [], []\n",
    "        pair = {}\n",
    "        pre = -1\n",
    "        for i, c in enumerate(s):\n",
    "            if c == '{':\n",
    "                pre = i\n",
    "            elif c == '}':\n",
    "                pair[pre] = i\n",
    "        # print(pair)\n",
    "        n = len(s)\n",
    "        def dfs(index, ele):\n",
    "            if index >= n:\n",
    "                ans.append(''.join(ele))\n",
    "                return\n",
    "            if s[index] == '{':\n",
    "                for i in range(index + 1, pair[index], 2):\n",
    "                    ele.append(s[i])\n",
    "                    dfs(pair[index] + 1, ele)\n",
    "                    ele.pop()\n",
    "            else:\n",
    "                ele.append(s[index])\n",
    "                dfs(index + 1, ele)\n",
    "                ele.pop()\n",
    "        dfs(0, ele)\n",
    "        return sorted(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        arr=[]\n",
    "        #先分组再回溯\n",
    "        pre,flag=[],0\n",
    "        for v in s:\n",
    "            if v==\",\": continue\n",
    "            if v.isalpha():\n",
    "                pre.append(v)\n",
    "                if not flag:\n",
    "                    arr.append(pre.copy())\n",
    "                    pre.clear()\n",
    "            elif v==\"{\":\n",
    "                flag=1\n",
    "            else:\n",
    "                flag=0\n",
    "                arr.append(pre.copy())\n",
    "                pre.clear()\n",
    "        n=len(arr)\n",
    "        ans,path=[],[]\n",
    "        #分组完成,开始回溯\n",
    "        def traceback(i):\n",
    "            if i==n:\n",
    "                ans.append(\"\".join(path))\n",
    "                return\n",
    "            for ch in arr[i]:\n",
    "                path.append(ch)\n",
    "                traceback(i+1)\n",
    "                path.pop()\n",
    "        traceback(0)\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        dic = {}\n",
    "        stack = []\n",
    "        i, n = 0, len(s)\n",
    "        while i < n:\n",
    "            if s[i] == \"{\":\n",
    "                stack.append(i)\n",
    "            elif s[i] == \"}\":\n",
    "                dic[stack.pop()] = i\n",
    "            i += 1\n",
    "        if not dic:\n",
    "            return [s]\n",
    "        \n",
    "        self.ans = []\n",
    "        def backtrace(s, n, idx, lst, dic):\n",
    "            if idx == n:\n",
    "                self.ans.append(\"\".join(lst))\n",
    "                return\n",
    "            if s[idx] != \"{\":\n",
    "                lst.append(s[idx])\n",
    "                backtrace(s, n, idx + 1, lst, dic)\n",
    "                lst.pop()\n",
    "            else:\n",
    "                j = dic[idx]\n",
    "                for c in s[idx + 1: j].split(\",\"):\n",
    "                    lst.append(c)\n",
    "                    backtrace(s, n, j + 1, lst, dic)\n",
    "                    lst.pop()\n",
    "                \n",
    "        backtrace(s, n, 0, [], dic)\n",
    "        self.ans.sort()\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, s: str) -> List[str]:\n",
    "        def dfs(prefix:str, s:str) ->None:\n",
    "            #--剪枝\n",
    "            if not s:\n",
    "                self.res.append(prefix)\n",
    "                return\n",
    "            #--第一个是’{‘\n",
    "            if s[0].isalpha() == 0:\n",
    "                tmp =''\n",
    "                i = 0\n",
    "                while i < len(s):\n",
    "                    if s[i] == '}':\n",
    "                        tmp = s[1:i]\n",
    "                        break\n",
    "                    i +=1\n",
    "                tmp = tmp.split(',')\n",
    "                tmp.sort()\n",
    "                for c in tmp:\n",
    "                    dfs(prefix + c, s[i+1:])\n",
    "            #--第一个是字母\n",
    "            else:\n",
    "                i = 0\n",
    "                while i < len(s):\n",
    "                    if s[i] == \"{\":\n",
    "                        break\n",
    "                    i += 1\n",
    "                dfs(prefix+s[:i], s[i:])\n",
    "        \n",
    "        self.res=[]\n",
    "        dfs(\"\",s)\n",
    "        return self.res\n",
    "\n",
    "\n",
    "    "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
